//
// Created by f12160c on 2018/7/26.
//

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

#include "leetcode/leetcode.hpp"

using namespace std;

void build_result(vector<string> &ret, string stack, int n, int level)
{
    auto expect = stack.size() + level;
    if(n < expect){

    }
    else if(n == expect){
        stack.resize(n, ')');
        ret.push_back(stack);
    }
    else {
        build_result(ret, stack + '(', n, level + 1);
        if(level){
            build_result(ret, stack + ')', n, level - 1);
        }
    }
}

vector<string> Solution::generateParenthesis(int n)
{
    vector<string> ret;
    string stack;

    build_result(ret, stack, 2*n, 0);
    return ret;
}